\documentclass[10pt]{article}
\usepackage{amsmath}

\newcommand{\problem}[1]{\noindent{\sc Problem #1.}}
\newcommand{\solution}{\noindent{\sc Solution.}}
\newcommand{\complexity}{\noindent{\sc Complexity. }}
\newcommand{\answer}{\noindent{\sc Answer. }}

\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}

\begin{document}

\problem{201} 
Subsets with a unique sum.

For any set $A$ of numbers, let $S(A)$ be the sum of the elements of $A$.

Consider the set $B = \{1,3,6,8,10,11\}$. There are 20 subsets of $B$ containing three elements, and their sums are:
\begin{align}
S(\{1,3,6\}) = 10 \notag \\
S(\{1,3,8\}) = 12 \notag \\
S(\{1,3,10\}) = 14 \notag \\
S(\{1,3,11\}) = 15 \notag \\
S(\{1,6,8\}) = 15 \notag \\
S(\{1,6,10\}) = 17 \notag \\
S(\{1,6,11\}) = 18 \notag \\
S(\{1,8,10\}) = 19 \notag \\
S(\{1,8,11\}) = 20 \notag \\
S(\{1,10,11\}) = 22 \notag \\
S(\{3,6,8\}) = 17 \notag \\
S(\{3,6,10\}) = 19 \notag \\
S(\{3,6,11\}) = 20 \notag \\
S(\{3,8,10\}) = 21 \notag \\
S(\{3,8,11\}) = 22 \notag \\
S(\{3,10,11\}) = 24 \notag \\
S(\{6,8,10\}) = 24 \notag \\
S(\{6,8,11\}) = 25 \notag \\
S(\{6,10,11\}) = 27 \notag \\
S(\{8,10,11\}) = 29 \notag
\end{align}
Some of these sums occur more than once, others are unique.

For a set $A$, let $U(A,k)$ be the set of unique sums of $k$-element subsets of $A$, in our example we find $U(B,3) = \{10,12,14,18,21,25,27,29\}$ and $S(U(B,3)) = 156$.

Now consider the 100-element set $I = \{1^2, 2^2, ... , 100^2\}$.
$I$ has about $10^{29}$ 50-element subsets.

Determine the sum of all integers which are the sum of exactly one of the 50-element subsets of $I$, i.e. find $S(U(I,50))$.

\solution

Our algorithm is pretty straightforward: we count the number of ways to construct each possible sum from the subsets, and find those sums with only one way to construct it. To implement this, we check each element in the set in order. For each element, we find out all the possible sums that can be constructed from this element and the elements before it. Once the entire set is traversed, it is easy to filter out the unique sums.

Formally, let $A$ denote the set in question, and $N=|A|$ be the number of elements in $A$. Let $C(m,k; n)$, where $0 \le m \le S(A), 1 \le k \le n \le N$, be the number of ways an integer $m$ can be constructed as the sum of $k$ distinct elements from the first $n$ elements of set $A$. We note the following recursive relation for $C(m,k; n)$:
\[
C(m, k; n) = C(m, k; n-1) + C(m-a_n, k-1; n-1)
\]
with boundary condition $C(0, 0; 0) = 1$. And the $k$-element unique-sum set of $A$ is simply
\[
U(A, k) = \{m \,|\, C(m, k; N) = 1\}
\]

We compute $C(m,k; N)$ by the following steps (dynamic programming):

1) Initialize $C_{m,k}$ to zero. Let $C_{0,0} = 1$.

2) Take the next element $a$ from $A$. If there are no more elements, then finish.

3) For each $C_{m,k} > 0$, let $C_{m+a,k+1} = C_{m+a,k+1} + C_{m,k}$. We need to do this from the largest $m$ to the smallest $m$.

4) Go to step 2.

There are a few optimizations that can be employed in the implementation. First, since we only care about whether $C_{m,k}=1$, we only need to store three states for $C_{m,k}$: 0 if the sum cannot be constructed from $k$ elements, 1 if there is a unique way to construct it, or 2 if there are more than one way to construct it. This not only saves memory (only 2 bits needed for each $C_{m,k}$) but also avoids integer overflow problems when we do the addition.

Second, since the problem only asks for the unique-sum subsets of a given size $K$, we don't need to calculate or store $C_{m,k}$ where $k > K$. And since the sum of $K$ elements of set $A$ cannot exceed the sum of the $K$ largest elements of $A$ (denoted as $M$), we don't need to store $C_{m,k}$ where $m > M$.

Lastly, for the particular parameters of this problem, where there are 100 elements in the set and we are looking for unique-sum subsets of 50 elements, we note that if $B$ is a unique-sum set of 50 elements, then its complement set, $B^c$, must also be a unique-sum set of 50 elements. That is, the unique-sum subsets come in pairs. We also note that $S(B)+S(B^c)=S(A)$, so without loss of generality we can assume $S(B) < S(A)/2$. This means we only need to compute $C_{m,k}$ for $m < S(A)/2$, and the sum of unique sums will be $S(A)$ multiplied by the number of unique-sum sets found.

In the actual implementation, some programming tricks are applied under the assumption that $K \le 63$, which enables us to use two 64-bit integers to store all $C_{m,k}$ for a given $m$, as well as to implement the additions with bitwise operations.

\answer
115039000.

\complexity

Time complexity: $\mathcal{O}(n S(A) \log{K})$

Space complexity: $\mathcal{O}(S(A) \log{K})$

\end{document} 